package DoExercise.左程云基础班;

public class Code_01_认识复杂度对数器二分法与异或运算
{

    /***
     * arr中，只有一种数字出现了奇数次，其他数字都出现了偶数次，怎么找到并打印这个数字
     * 异或运算满足交换率和结合率
     */
    public static void printOddTimesNum1(int[] arr)
    {
        int eor = 0;
        for (int i = 0; i < arr.length; i++)
        {
            eor ^= arr[i];
        }
        System.out.println(eor);
    }

    /**
     * arr中，有2种数字出现了奇数次，其他数字都出现了偶数次，怎么找到并打印这个数字
     *
     * @param arr
     */
    public static void printOddTimesNum2(int[] arr)
    {
        int eor = 0;
        for (int i = 0; i < arr.length; i++)
        {
            eor ^= arr[i];//包含2个奇数相^的结果
        }
        int rightOne = eor & (~eor + 1);/**小技巧：如何提取一个int类型的数最右侧的1。*/
        int onlyOne = 0;
        for (int i = 0; i < arr.length; i++)
        {
            if ((arr[i] & rightOne) != 0)
            {
                onlyOne ^= arr[i];
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }

    /**
     *
     * 统计一个数字二进制位上共有多少个1
     *
     * @param number
     * @return
     */
    public static int bit1Counts(int number)
    {
        int counts = 0;
        while (number != 0)
        {
            int rightOne = number & ((~number) + 1);
            counts++;
            number ^= rightOne;//将最右侧的1去掉
        }
        return counts;
    }

    public static void main(String[] args)
    {
        //        int[] arr = {1, 2, 3, 3, 3, 2, 1, 1};
        //        printOddTimesNum1(arr);

        //        int[] arr = {1,1,2,2,3,3,5,7};
        //        printOddTimesNum2(arr);
//        System.out.println(bit1Counts(7));
        int a = 1210,b = 1210,d = 1210;
        int c = a ^ b ^ d;
        System.out.println(c);
    }

}
